CODE 35. Validate Binary Search Tree

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 35 Validate Binary Search Tree/

访问原文「CODE 35. Validate Binary Search Tree」

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

confused what "{1,#,2,3}" means? >
read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:

  1
 / \
2   3
   /
  4
   \
    5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

public boolean isValidBST(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == root) {
		return true;
	}
	Stack<TreeNode> stack = new Stack<TreeNode>();
	TreeNode pre = new TreeNode(Integer.MIN_VALUE);
	TreeNode now = root;
	while (!stack.isEmpty() || null != now) {
		if (null == now) {
			now = stack.pop();
			if (pre.val >= now.val) {
				return false;
			}
			pre = now;
			now = now.right;
		} else {
			stack.push(now);
			now = now.left;
		}
	}
	return true;
}